package com.github.yangyishe.p100;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 15. 三数之和
 * https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 *
 * 你返回所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 *
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。
 * 示例 2：
 *
 * 输入：nums = [0,1,1]
 * 输出：[]
 * 解释：唯一可能的三元组和不为 0 。
 * 示例 3：
 *
 * 输入：nums = [0,0,0]
 * 输出：[[0,0,0]]
 * 解释：唯一可能的三元组和为 0 。
 *
 *
 * 提示：
 *
 * 3 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 */
public class Problem15 {
    public static void main(String[] args) {
//        int[] arr={34,55,79,28,46,33,2,48,31,-3,84,71,52,-3,93,15,21,-43,57,-6,86,56,94,74,83,-14,28,-66,46,-49,62,-11,43,65,77,12,47,61,26,1,13,29,55,-82,76,26,15,-29,36,-29,10,-70,69,17,49};
        int[] arr={-1,0,1,2,-1,-4};

        Problem15 problem15 = new Problem15();
//        problem15.redixSort(arr);
//        System.out.println(Arrays.toString(arr));

//        int i = problem15.inserValueSearch(arr, 0, arr.length - 1, 0);
//        System.out.println(i);

        List<List<Integer>> lists = problem15.threeSum(arr);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }

    }

    /**
     * 最新思路:
     * 按照灵茶山艾府的思想, 每次遍历获取的信息量能达到O(n), 会使时间复杂度变为O(n^2)
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums){
        // 先排序
        Arrays.sort(nums);

        List<List<Integer>> resultList=new ArrayList<>();
        // 再遍历
        for(int i=0;i<nums.length-2;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            if(nums[i]+nums[nums.length-1]+nums[nums.length-2]<0){
                continue;
            }
            if(nums[i]+nums[i+1]+nums[i+2]>0){
                break;
            }
            int left=i+1;
            int right=nums.length-1;
            while(left<right){
                if(left>i+1&&nums[left]==nums[left-1]){
                    left++;
                    continue;
                }
                if(right<nums.length-1&&nums[right]==nums[right+1]){
                    right--;
                    continue;
                }
                int result=nums[i]+nums[left]+nums[right];
                if(result==0){
                    resultList.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                    continue;
                }
                if(result>0){
                    right--;
                }else{
                    left++;
                }
            }
        }

        return resultList;
    }

    /**
     * 思路:
     * 1. 先对数组进行排序. 考虑到数组最大为3000, 可采用基数排序
     * 2. 第一元素从下标0开始, 第二元素从下标1开始, 计算出第三元素值, 并通过差值查找快速找到对应索引值
     * 3. 遍历原则: 每个元素, 均翻到下一个不同值的下标, 但不同元素可以使用相同值的不同下标
     * @param nums
     * @return
     */
//    public List<List<Integer>> threeSum(int[] nums) {
//        redixSort(nums);
//        System.out.println(Arrays.toString(nums));
//
//        List<List<Integer>> resultList=new ArrayList<>();
//
//        int index1=0;
//        int index2=1;
//        int predictVal3;
//        while(index1<nums.length-1&&index1!=-1){
//            predictVal3=-nums[index1]-nums[index2];
//            int i = inserValueSearch(nums, index2+1, nums.length - 1, predictVal3);
//            if(i!=-1){
//                resultList.add(Arrays.asList(nums[index1],nums[index2],nums[i]));
//            }
//            index2=nextDifferValIndex(nums,index2);
//
//            if (index2==-1||index2>nums.length) {
//                index1=nextDifferValIndex(nums,index1);
//                index2=index1+1;
//            }
//        }
//
//        return resultList;
//    }
//
//    public void redixSort(int[] nums){
//        // 需要准备20个桶(因为有负数)
//        // 预计需要排5次桶
//        int[][] bucketContent=new int[20][nums.length];
//        int[] bucketCount=new int[20];
//
//        // ws=0
//        int wsv=1;
//        int bucketIndex;
//        int temp;
//
//        while(wsv<100000){
//            for (int num : nums) {
//                temp=num/wsv%10;
//                bucketIndex=bucketIndex(temp,num<0);
//                bucketContent[bucketIndex][bucketCount[bucketIndex]]=num;
//                bucketCount[bucketIndex]++;
//            }
//            temp=0;
//            for (int i=0;i<bucketCount.length;i++) {
//                if(bucketCount[i]>0){
//                    for(int j=0;j<bucketCount[i];j++){
//                        nums[temp++]=bucketContent[i][j];
//                    }
//                    bucketCount[i]=0;
//                }
//            }
//            wsv*=10;
//        }
//
//
//    }
//
//    public int bucketIndex(int dwv,boolean isNeg){
//        if(isNeg){
//            return 9+dwv;
//        }else{
//            return 10+dwv;
//        }
//    }
//
//    public int inserValueSearch(int[] nums,int leftBnd,int rightBnd,int val){
//        if(leftBnd>rightBnd){
//            return -1;
//        }
//        if(nums[leftBnd]>val||nums[rightBnd]<val){
//            return -1;
//        }
//        if(nums[leftBnd]==nums[rightBnd]){
//            if(nums[leftBnd]==val){
//                return leftBnd;
//            }else{
//                return -1;
//            }
//        }
//        int newIndex=leftBnd+(val-nums[leftBnd])*(rightBnd-leftBnd)/(nums[rightBnd]-nums[leftBnd]);
//        if(nums[newIndex]==val){
//            return newIndex;
//        }else if(nums[newIndex]>val){
//            return inserValueSearch(nums,leftBnd,newIndex-1,val);
//        }else{
//            return inserValueSearch(nums,newIndex+1,rightBnd,val);
//        }
//
//    }
//
//    public int nextDifferValIndex(int[] nums,int index){
//        int temp=nums[index];
//        for(int i=index+1;i<nums.length;i++){
//            if(temp!=nums[i]){
//                return i;
//            }
//        }
//        return -1;
//    }
}
